home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 333_02 / regex2.c < prev    next >
C/C++ Source or Header  |  1989-04-21  |  14KB  |  482 lines
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "awk.h"
  6.  
  7.  
  8. /* Like re_match but tries first a match starting at index `startpos',      */
  9. /* then at startpos + 1, and so on.  `range' is the number of places to try */
  10. /* before giving up.  If `range' is negative, the starting positions tried  */
  11. /* are startpos, startpos - 1, etc.  It is up to the caller to make sure    */
  12. /* that range is not so large as to take the starting position outside of   */
  13. /* the input strings.  The value returned is the position at which the        */
  14. /* match was found, or -1 if no match was found.                */
  15.  
  16. int PASCAL re_search(REPAT_BUFFER *pbufp, char *string, int size,
  17.              int startpos, int range, REREGS *regs)
  18. {
  19.     register char      *fastmap   = pbufp->fastmap;
  20.  
  21.     /* Update the fastmap now if not correct already */
  22.     if (fastmap && !pbufp->fastmap_accurate)
  23.     re_compile_fastmap(pbufp);
  24.  
  25.     while (TRUE)
  26.     {
  27.     /* If a fastmap is supplied, skip quickly over characters that        */
  28.     /* cannot possibly be the start of a match. Note, however, that if  */
  29.     /* the pattern can possibly match the null string, we must test it  */
  30.     /* at each starting point so that we take the first null string we  */
  31.     /* get.                                 */
  32.     if (fastmap && startpos < size && pbufp->can_be_null != 1)
  33.     {
  34.         if (range > 0)
  35.         {
  36.         register int      lim = 0;
  37.         register char     *p;
  38.         auto     int      irange = range;
  39.  
  40.         if (startpos < size && startpos + range >= size)
  41.             lim = range - (size - startpos);
  42.  
  43.         p = &string[startpos];
  44.         while (range > lim && !fastmap[*p++])
  45.             range--;
  46.         startpos += irange - range;
  47.         }
  48.         else
  49.         {
  50.         register char   c;
  51.  
  52.         c = string[startpos];
  53.         if (!fastmap[c])
  54.             goto advance;
  55.         }
  56.     }
  57.  
  58.     if (range >= 0 && startpos == size
  59.         && fastmap && pbufp->can_be_null == 0)
  60.         return(-1);
  61.  
  62.     if (0 <= re_match(pbufp, string, size, startpos, regs))
  63.         return(startpos);
  64. advance:
  65.     if (!range)
  66.         break;
  67.     if (range > 0)
  68.     {
  69.         --range;
  70.         ++startpos;
  71.     }
  72.     else
  73.     {
  74.         ++range;
  75.         --startpos;
  76.     }
  77.     }
  78.     return(-1);
  79. }
  80.  
  81.  
  82. /* Match the pattern described by `pbufp' against data which is the virtual  */
  83. /* concatenation of `string1' and `string2'.  `size1' and `size2' are the    */
  84. /* sizes of the two data strings.  Start the match at position `pos'.    Do  */
  85. /* not consider matching past the position `mstop'.  If pbufp->fastmap is    */
  86. /* nonzero, then it had better be up to date.                     */
  87. /*                                         */
  88. /* The reason that the data to match is specified as two components which    */
  89. /* are to be regarded as concatenated is so that this function can be used   */
  90. /* directly on the contents of an Emacs buffer.  -1 is returned if there is  */
  91. /* no match.  Otherwise the value is the length of the substring which was   */
  92. /* matched.                                     */
  93.  
  94. int PASCAL re_match(REPAT_BUFFER *pbufp, char *string, int size,
  95.             int pos, REREGS *regs)
  96. {
  97.     register int      op;
  98.     register char     *p    = pbufp->buffer;
  99.     register char     *pend = p + pbufp->used;
  100.     auto     char     *end;               /* end of string */
  101.     auto     char     *end_match;
  102.     register char     *d, *dend;
  103.     register int      mcnt;
  104.  
  105.     /* Failure point stack.  Each place that can handle a failure further
  106.      * down the line pushes a failure point on this stack.  It consists of
  107.      * two char *'s. The first one pushed is where to resume scanning the
  108.      * pattern; the second pushed is where to resume scanning the strings. If
  109.      * the latter is zero, the failure point is a "dummy". If a failure
  110.      * happens and the innermost failure point is dormant, it discards that
  111.      * failure point and tries the next one. */
  112.  
  113.     static   int      stacksiz = 0;
  114.     static   char    **stackb   = NULL;
  115.     auto     char    **stackp, **stacke;
  116.  
  117.     /* Information on the "contents" of registers. These are pointers into
  118.      * the input strings; they record just what was matched (on this attempt)
  119.      * by some part of the pattern. The start_memory command stores the start
  120.      * of a register's contents and the stop_memory command stores the end. 
  121.      *
  122.      * At that point, regstart[regnum] points to the first character in the
  123.      * register, regend[regnum] points to the first character beyond the end
  124.      * of the register, and regstart_segend[regnum] is either the same as
  125.      * regend[regnum] or else points to the end of the input string into
  126.      * which regstart[regnum] points. The latter case happens when
  127.      * regstart[regnum] is in string1 and regend[regnum] is in string2.  */
  128.  
  129.     auto     char     *regstart[RE_NREGS];
  130.     auto     char     *regstart_segend[RE_NREGS];
  131.     auto     char     *regend[RE_NREGS];
  132.     static   char      outmem_msg[] = "Out of memory in re_match()";
  133.  
  134.  
  135.     if (0 == stacksiz)
  136.     {
  137.     stacksiz = 2 * NFAILURES;
  138.     if (NULL == (stackb = (char **) malloc(stacksiz * sizeof(char *))))
  139.         panic(outmem_msg);
  140.     }
  141.     stackp = stackb;
  142.     stacke = stackb + stacksiz;
  143.  
  144.     end = string + size;
  145.  
  146.     /* Compute where to stop matching, within the two strings */
  147.     end_match = string + size;
  148.  
  149.     /* Initialize \( and \) text positions to -1 to mark ones that no \( or */
  150.     /* \) has been seen for.                            */
  151.     for (mcnt = 0; mcnt < sizeof(regstart) / sizeof(*regstart); mcnt++)
  152.     regstart[mcnt] = (char *) -1;
  153.  
  154.     /* `p' scans through the pattern as `d' scans through the data. `dend' is
  155.      * the end of the input string that `d' points within. `d' is advanced
  156.      * into the following input string whenever necessary, but this happens
  157.      * before fetching; therefore, at the beginning of the loop, `d' can be
  158.      * pointing at the end of a string, but it cannot equal string2.  */
  159.  
  160.     d     = string + pos;
  161.     dend = end_match;
  162.  
  163.     /* This loop loops over pattern commands. It exits by returning from the
  164.      * function if match is complete, or it drops through if match fails at
  165.      * this starting point in the input data. */
  166.  
  167.     while (TRUE)
  168.     {
  169.     if (p == pend)
  170.         /* End of pattern means we have succeeded! */
  171.     {
  172.         /* If caller wants register contents data back, convert it to
  173.          * indices */
  174.         if (regs)
  175.         {
  176.         regend[0]   = d;
  177.         regstart[0] = string;
  178.         for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
  179.         {
  180.             if ((mcnt != 0) && regstart[mcnt] == (char *) -1)
  181.             {
  182.             regs->start[mcnt] = -1;
  183.             regs->end[mcnt] = -1;
  184.             continue;
  185.             }
  186.             regs->start[mcnt] = regstart[mcnt] - string;
  187.             regs->end[mcnt] = regend[mcnt] - string;
  188.         }
  189.         regs->start[0] = pos;
  190.         }
  191.         return(d - string - pos);
  192.     }
  193.  
  194.     /* Otherwise match next pattern command */
  195.     op = *p++;
  196.     switch (op)
  197.     {
  198.         /* \( is represented by a start_memory, \) by a stop_memory.
  199.          * Both of those commands contain a "register number"
  200.          * argument. The text matched within the \( and \) is
  201.          * recorded under that number. Then, \<digit> turns into a
  202.          * `duplicate' command which is followed by the numeric value
  203.          * of <digit> as the register number. */
  204.  
  205.         case RECODE_START_MEMORY:
  206.         regstart[*p] = d;
  207.         regstart_segend[*p++] = dend;
  208.         break;
  209.  
  210.         case RECODE_STOP_MEMORY:
  211.         regend[*p] = d;
  212.         if (regstart_segend[*p] == dend)
  213.             regstart_segend[*p] = d;
  214.         p++;
  215.         break;
  216.  
  217.         case RECODE_DUPLICATE:
  218.         {
  219.             int         regno = *p++;    /* Get which register to
  220.                               * match against */
  221.             register char  *d2, *dend2;
  222.  
  223.             d2 = regstart[regno];
  224.             dend2 = regstart_segend[regno];
  225.             while (TRUE)
  226.             {
  227.             /* At end of register contents => success */
  228.             if (d2 == dend2)
  229.                 break;
  230.  
  231.             /* mcnt gets # consecutive chars to compare */
  232.             mcnt = dend - d;
  233.             if (mcnt > dend2 - d2)
  234.                 mcnt = dend2 - d2;
  235.             /* Compare that many; failure if mismatch, else skip
  236.              * them. */
  237.             if (bcmp(d, d2, mcnt))
  238.                 goto fail;
  239.             d += mcnt, d2 += mcnt;
  240.             }
  241.         }
  242.         break;
  243.  
  244.         case RECODE_ANYCHAR:
  245.         /* Match anything but a newline.  */
  246.         if (*d++ == '\n')
  247.             goto fail;
  248.         break;
  249.  
  250.         case RECODE_CHARSET:
  251.         case RECODE_CHARSET_NOT:
  252.         {
  253.             /* Nonzero for cha